/*
 * symboltable.c
 *
 *  Created on: 2013-5-4
 *      Author: xkaying
 */

#include "symboltable.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "stack.h"

#define SymbolTable_MaxHash 1024*16
#define SymbolTable_HalfHash 1024*8 //hash表的一半,减少冲突概率,只存放一半的数据
#define SymbolTable_MaxPage 1024*32 //一个页面32k
//符号表节点,每个节点,可以存放10240个符号足够使用了,不够,分配新节点

typedef struct _symboltablepage
{
	int use; //使用到哪个点
	char buff[SymbolTable_MaxPage];
} SymbolTablePage;

typedef struct _symboltablenode
{
	//符号表索引 1024*16//一万六千多个符号
	char **hash;
	//符号表缓冲空间
	Stack *pbuff;
	int use;
} SymbolTableNode;

SymbolTableNode *SymbolTableNodeInit()
{
	SymbolTableNode *pnode;
	pnode = (SymbolTableNode*) malloc(sizeof(SymbolTableNode*));
	pnode->hash = (char**) calloc(SymbolTable_MaxHash, sizeof(char*));
	pnode->pbuff = StackInit(0);
	SymbolTablePage *ppage;
	ppage = (SymbolTablePage*) malloc(sizeof(SymbolTablePage));
	ppage->use = 0;
	StackPush(pnode->pbuff, ppage);
	pnode->use = 0;
	return pnode;
}

//符号表
struct _symboltable
{
	//使用堆栈进行存储
	Stack *nodestack;
};

SymbolTable *ptable = 0;

unsigned time33(char *str)
{
	int len;
	len = strlen(str);
	unsigned long hash = 0;
	for (int i = 0; i < len; i++) {
		hash = hash * 33 + (unsigned long) str[i];
	}
	return hash;
}

char *SymbolTablePush(char *str)
{
	assert(str);
	SymbolTableNode *pnode;
	if (ptable == 0) {
		ptable = (SymbolTable*) malloc(sizeof(SymbolTable));

		pnode = SymbolTableNodeInit();
		ptable->nodestack = StackInit();
		StackPush(ptable->nodestack, pnode);
	}
	//查找是否存在相同的str
	StackCursor *pcursor;
	pcursor = StackGetCursor(ptable->nodestack);
	pnode = (SymbolTableNode*) StackForeach(ptable->nodestack, pcursor);
	unsigned hashcode;
	hashcode= time33(str) % SymbolTable_MaxHash;
	unsigned hash;
	hash=hashcode;
	while (pnode) {
		while (pnode->hash[hashcode]) {
			if (!strcmp(pnode->hash[hashcode], str)) {
				return pnode->hash[hashcode];
			}
			//查找下一个
			hashcode++;
			if (hashcode == SymbolTable_MaxHash) {
				hashcode = 0;
			}
		}
		pnode = (SymbolTableNode*) StackForeach(ptable->nodestack, pcursor);
	}
	//
	pnode = (SymbolTableNode*) StackData(ptable->nodestack);
	//表示不存在,检查hash空间是否满了
	if (pnode->use >= SymbolTable_HalfHash) {
		//分配新的节点
		pnode = SymbolTableNodeInit();
		StackPush(ptable->nodestack, pnode);
	}
	int len;
	len = strlen(str);
	//检查pnode的当前page是否满了
	SymbolTablePage *ppage;
	ppage = ((SymbolTablePage*) StackData(pnode->pbuff));
	if (ppage->use + len >= SymbolTable_MaxPage) {
		//表示空间不够,需要分配新的
		SymbolTablePage *ppage;
		ppage = (SymbolTablePage*) malloc(sizeof(SymbolTablePage));
		ppage->use = 0;
		StackPush(pnode->pbuff, ppage);
	}

	//获取hash地址
		while (pnode->hash[hash]) {
			hash++;
			if (hash == SymbolTable_MaxHash) {
				hash = 0;
			}
		}
	char *ret;
	//进行赋值和返回操作
	ret = ppage->buff + ppage->use;
	strcpy(ret, str);
	ppage->use += len;
	ppage->buff[ppage->use] = '\0';
	ppage->use++;
	pnode->hash[hash]=ret;
	return ret;
}

